We show that detecting real roots for honestly n-variate (n+2)-nomials (withinteger exponents and coefficients) can be done in time polynomial in thesparse encoding for any fixed n. The best previous complexity bounds wereexponential in the sparse encoding, even for n fixed. We then give acharacterization of those functions k(n) such that the complexity of detectingreal roots for n-variate (n+k(n))-nomials transitions from P to NP-hardness asn tends to infinity. Our proofs follow in large part from a new complexitythreshold for deciding the vanishing of A-discriminants of n-variate(n+k(n))-nomials. Diophantine approximation, through linear forms inlogarithms, also arises as a key tool.
展开▼
